// =================================================================
// SIMPLIFICATION
// =================================================================

void Mesh::Simplification(int target_tri_count) 
{
  // clear out any previous relationships between vertices
  vertex_parents.clear();

  printf ("Simplify the mesh! %d -> %d\n", numTriangles(), target_tri_count);
  map<float,Edge*> legal_edges;
  for (triangleshashtype::iterator iter = triangles.begin(); iter != triangles.end(); iter++) 
  {
	Triangle *t = iter->second;   //GET THE THREE VERTICES
		
	Edge *e = t->getEdge();
	Edge *temp=e;
	//Vertex *v = e->getStartVertex();
	//Vertex *vE = e->getEndVertex();
	vector<Triangle*> nearby_triangles;
	nearby_triangles.push_back(t);

	Edge *e_next = e->getNext();
	Edge *temp2=e_next;
	//Vertex *v2 = e_next->getStartVertex();
	//Vertex *v2E = e_next->getEndVertex();
	vector<Triangle*> nearby_triangles2;
	nearby_triangles2.push_back(t);

	Edge *e_next_next = e_next->getNext();
	Edge *temp3 = e_next_next;
	//Vertex *v3 = e_next_next->getStartVertex();
	//Vertex *v3E = e_next_next->getEndVertex();
	vector<Triangle*> nearby_triangles3;
	nearby_triangles3.push_back(t);
	
	/*temp=e->getOpposite();
	Triangle *t2=temp->getTriangle();
	nearby_triangles.push_back(t2);
	temp2=e->getOpposite();
	Triangle *t2b=temp2->getTriangle();
	nearby_triangles.push_back(t2b);
	temp3=e->getOpposite();
	Triangle *t2c=temp3->getTriangle();
	nearby_triangles.push_back(t2c);*/
	cout<<"Jefferson"<<endl;
	int count=0;
	do  //FIND THE TRIANGLES SURROUNDING EACH VERTEX
	{
		//Edge *tempx = ( (temp->getNext())->getOpposite() );
		temp= ( ((temp->getNext())-> getNext())-> getOpposite());
		Triangle *t1 = temp->getTriangle();
		nearby_triangles.push_back(t1);
		//cout<<"1"<<endl;
		count++;
		if(count>=10)
			break;
	}
	while( &(nearby_triangles[nearby_triangles.size()-1]->getEdge()->getStartVertex()->getPos()) != &(e->getStartVertex()->getPos()) );
	count=0;
	do
	{
		temp2= ( ((temp2->getNext())-> getNext())-> getOpposite());
		Triangle *t1 = temp2->getTriangle();
		nearby_triangles2.push_back(t1);
		//cout<<"2"<<endl;
		count++;
		if(count>=10)
			break;
	}
	while( &(nearby_triangles2[nearby_triangles2.size()-1]->getEdge()->getStartVertex()->getPos()) != &(e_next->getStartVertex()->getPos()) );
	count=0;
	do
	{
		temp3= ( ((temp3->getNext())-> getNext())-> getOpposite());
		Triangle *t1 = temp3->getTriangle();
		nearby_triangles3.push_back(t1);
		//cout<<"3"<<endl;
		count++;
		if(count>=10)
			break;
	}
	while( &(nearby_triangles3[nearby_triangles3.size()-1]->getEdge()->getStartVertex()->getPos()) != &(e_next_next->getStartVertex()->getPos()) );
	cout<<"Gay"<<endl;
	
	vector<Vec3f> nearby_verts;  //STORE THE VERTICES OF THE TRIANGLES FOR COMPARISON CHECK
	for(int i=0; i<nearby_triangles.size(); i++)
	{
		Edge *an_edge=nearby_triangles[i]->getEdge();
		nearby_verts.push_back(an_edge->getStartVertex()->getPos());
		nearby_verts.push_back(an_edge->getEndVertex()->getPos());
		an_edge=an_edge->getNext();
		nearby_verts.push_back(an_edge->getEndVertex()->getPos());
	}
	vector<Vec3f> nearby_verts2;
	for(int i=0; i<nearby_triangles2.size(); i++)
	{
		Edge *an_edge=nearby_triangles2[i]->getEdge();
		nearby_verts2.push_back(an_edge->getStartVertex()->getPos());
		nearby_verts2.push_back(an_edge->getEndVertex()->getPos());
		an_edge=an_edge->getNext();
		nearby_verts2.push_back(an_edge->getEndVertex()->getPos());
	}
	vector<Vec3f> nearby_verts3;
	for(int i=0; i<nearby_triangles3.size(); i++)
	{
		Edge *an_edge=nearby_triangles3[i]->getEdge();
		nearby_verts3.push_back(an_edge->getStartVertex()->getPos());
		nearby_verts3.push_back(an_edge->getEndVertex()->getPos());
		an_edge=an_edge->getNext();
		nearby_verts3.push_back(an_edge->getEndVertex()->getPos());
	}
	
	//check if 1st and 2nd, 2nd and 3rd, or 3rd and 1st groups of triangles share 20 or less vertices. If this is the case, add the edge.
	int counter=0;
	for(int i=0; i<nearby_verts.size(); i++)
		for(int j=0; j<nearby_verts2.size(); j++)
			if(nearby_verts[i]==nearby_verts[j])
				counter++;
	int counter2=0;
	for(int i=0; i<nearby_verts2.size(); i++)
		for(int j=0; j<nearby_verts3.size(); j++)
			if(nearby_verts2[i]==nearby_verts3[j])
				counter2++;
	int counter3=0;
	for(int i=0; i<nearby_verts3.size(); i++)
		for(int j=0; j<nearby_verts.size(); j++)
			if(nearby_verts3[i]==nearby_verts[j])
				counter3++;
				
	if(counter<=20)
		legal_edges[e->Length()]=e;
	if(counter2<=20)
		legal_edges[e_next->Length()]=e_next;
	if(counter3<=20)
		legal_edges[e_next_next->Length()]=e_next_next;
	cout<<"Yes"<<endl;
   }

	map<float,Edge*>::iterator iter;
	iter = legal_edges.begin();
	Edge* dead_edge=iter->second;
	delete dead_edge;
		
	
  }
  
  
  
if (args->gouraud) 
  {
	glBegin (GL_TRIANGLES);
	for (triangleshashtype::iterator iter = triangles.begin(); iter != triangles.end(); iter++) 
	{	
		Triangle *t = iter->second;
		
		Edge *e = t->getEdge();
		Edge *temp=e;
		Vertex *v = e->getStartVertex();
		vector<Vec3f> triangle_normals;
		
		Edge *e_next = e->getNext();
		Edge *temp2=e_next;
		Vertex *v2 = e_next->getStartVertex();
		vector<Vec3f> triangle_normals2;
		
		Edge *e_next_next = e_next->getNext();
		Edge *temp3 = e_next_next;
		Vertex *v3 = e_next_next->getStartVertex();
		vector<Vec3f> triangle_normals3;
		
		Vec3f a = (*t)[0]->getPos();
		Vec3f b = (*t)[1]->getPos();
		Vec3f c = (*t)[2]->getPos();
		Vec3f norm = ComputeNormal(a,b,c);
		triangle_normals.push_back(norm);
		triangle_normals2.push_back(norm);
		triangle_normals3.push_back(norm);
		
		do
		{
			Edge *tempx = ( (temp->getNext())->getOpposite() );
			temp=temp->getNext();
			Triangle *t1 = tempx->getTriangle();
			Vec3f a1 = (*t1)[0]->getPos();
			Vec3f b1 = (*t1)[1]->getPos();
			Vec3f c1 = (*t1)[2]->getPos();
			Vec3f norm1 = ComputeNormal(a1,b1,c1);
			triangle_normals.push_back(norm1);
		}
		while(temp!=e);
		do
		{
			Edge *tempx = ( (temp2->getNext())->getOpposite() );
			temp2=temp2->getNext();
			Triangle *t1 = tempx->getTriangle();
			Vec3f a1 = (*t1)[0]->getPos();
			Vec3f b1 = (*t1)[1]->getPos();
			Vec3f c1 = (*t1)[2]->getPos();
			Vec3f norm1 = ComputeNormal(a1,b1,c1);
			triangle_normals2.push_back(norm1);
		}
		while(temp2!=e_next);
		do
		{
			Edge *tempx = ( (temp3->getNext())->getOpposite() );
			temp3=temp3->getNext();
			Triangle *t1 = tempx->getTriangle();
			Vec3f a1 = (*t1)[0]->getPos();
			Vec3f b1 = (*t1)[1]->getPos();
			Vec3f c1 = (*t1)[2]->getPos();
			Vec3f norm1 = ComputeNormal(a1,b1,c1);
			triangle_normals3.push_back(norm1);
		}
		while(temp3!=e_next_next);
		
		Vec3f average,average2,average3;
		for(int i=0; i<triangle_normals.size(); i++)
			average+=triangle_normals[i];
		for(int i=0; i<triangle_normals2.size(); i++)
			average2+=triangle_normals2[i];
		for(int i=0; i<triangle_normals3.size(); i++)
			average3+=triangle_normals3[i];
			
		int ii=triangle_normals.size();
		int ii2=triangle_normals2.size();
		int ii3=triangle_normals3.size();
		
		average=Vec3f( (average.x()/ ii),(average.y()/ii),(average.z()/ii) );
		average2=Vec3f( (average2.x()/ ii2),(average2.y()/ii2),(average2.z()/ii2) );
		average3=Vec3f( (average3.x()/ ii3),(average3.y()/ii3),(average3.z()/ii3) );
		
		v->normal=average;
		v2->normal=average2;
		v3->normal=average3;
		
	}
	
	for (triangleshashtype::iterator iter = triangles.begin(); iter != triangles.end(); iter++) 
	{
		Triangle *t = iter->second;
		Vertex *a = (*t)[0];
		Vertex *b = (*t)[1];
		Vertex *c = (*t)[2];
		
		glNormal3f(a->normal.x(),a->normal.y(),a->normal.z());
		glVertex3f(a->x(),a->y(),a->z());
		glNormal3f(b->normal.x(),b->normal.y(),b->normal.z());
		glVertex3f(b->x(),b->y(),b->z());
		glNormal3f(c->normal.x(),c->normal.y(),c->normal.z());
		glVertex3f(c->x(),c->y(),c->z());
		
	}
	
   glEnd();
	
  } 
  
  
  
  
  
